package ArrayAndString;

public class Increase {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;  // 获取数组的长度

        // 如果数组长度小于3，无法存在递增的三元子序列，直接返回false
        if (n < 3) {
            return false;
        }

        // 创建一个数组 leftMin，用于存储每个元素左边的最小值
        int[] leftMin = new int[n];
        leftMin[0] = nums[0];  // 初始化第一个元素为数组的第一个元素

        // 遍历数组，计算每个元素左边的最小值并存储到 leftMin 数组中
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }

        // 创建一个数组 rightMax，用于存储每个元素右边的最大值
        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];  // 初始化最后一个元素为数组的最后一个元素

        // 从数组的倒数第二个元素开始向前遍历，计算每个元素右边的最大值并存储到 rightMax 数组中
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }

        // 遍历数组，查找是否存在满足条件的递增三元子序列
        for (int i = 1; i < n - 1; i++) {
            // 如果当前元素 nums[i] 大于左边的最小值 leftMin[i-1]
            // 且小于右边的最大值 rightMax[i+1]，则找到了递增三元子序列，返回true
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }

        // 如果没有找到递增三元子序列，则返回false
        return false;
    }
}
